package algorithms.leaning.class30;

import common.bean.TreeNode;
import common.util.MyUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 假设来到当前节点cur，开始时cur来到头节点位置
 * 1）如果cur没有左孩子，cur向右移动(cur = cur.right)
 * 2）如果cur有左孩子，找到左子树上最右的节点mostRight：
 * a.如果mostRight的右指针指向空，让其指向cur，
 * 然后cur向左移动(cur = cur.left)
 * b.如果mostRight的右指针指向cur，让其指向null，
 * 然后cur向右移动(cur = cur.right)
 * 3）cur为空时遍历停止
 *
 * @author guichang
 * @date 2021/7/3
 */

@SuppressWarnings("all")
public class Code1_二叉树_Morris遍历 {

    public static void main(String[] args) {
        TreeNode treeNode = MyUtil.createTreeNode(1, 2, 3, 4, 5, 6, 7);
        List<Integer> morris = morris(treeNode);
        MyUtil.printf("树的morris序: {}", morris);
    }

    public static List<Integer> morris(TreeNode head) {
        if (head == null) {
            return null;
        }
        List<Integer> res = new ArrayList<>();
        TreeNode curr = head;
        while (curr != null) {
            TreeNode mostRight = curr.left;
            // 有左树则找到右边界
            if (mostRight != null) {
                // 找右边界的时候不能到头或者跟当前节点相等
                while (mostRight.right != null && mostRight.right != curr) {
                    mostRight = mostRight.right;
                }
                // 第一次来到左树右边界
                if (mostRight.right == null) {
                    res.add(curr.val);
                    // 左树有边界的右节点指向当前节点
                    mostRight.right = curr;
                    // 当前节点向左移动
                    curr = curr.left;
                    continue;
                }
                // 第二次来到左树右边界
                else if (mostRight.right == curr) {
                    res.add(curr.val);
                    // 指向null，就是还原树结构
                    mostRight.right = null;
                }
            } else {
                // 记录无左树的节点
                res.add(curr.val);
            }
            // curr来到右节点
            curr = curr.right;
        }
        return res;
    }


}